package Wuli_2021;

import Wuli_2023.QuickSearch;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class ship_4 {
    public static void main(String[] args) {
        int[] wight = new int[]{10, 5, 30, 100, 2};
        int[] value = new int[]{100, 25, 60, 100, 100};
        List<int[]> ans = ship(wight, value, 20);
        return;
    }

    /**
     * 运走 的货物的价重比最大
     *
     * @param weight 第 i 种货物有 wi 吨,
     * @param value  价值是 Pi
     * @param M      最大载重量为 M 吨
     * @return
     */
    public static List<int[]> ship(int[] weight, int[] value, int M) {
        double[] perValue = new double[weight.length]; //每种货物每吨的价值
        for (int i = 0; i < weight.length; i++)
            perValue[i] = (double) value[i] / weight[i];
        //根据每吨货物的价值排序
        int[] index = new int[weight.length];
        for (int i = 0; i < index.length; i++) index[i] = i;
        sort(perValue, index, 0, perValue.length - 1);  //连带着货物一起排序
        List<int[]> result = new ArrayList<>();
        for (int i = 0; i < index.length; i++) {
            if (M > weight[index[i]]) {
                M = M - weight[index[i]];
                result.add(new int[]{index[i], weight[index[i]]});
            } else {
                result.add(new int[]{index[i], M});
                break;
            }
        }
        return result;
    }

    public static void sort(double[] perValue, int[] index, int low, int high) {
        if (low < high) {
            int pirot = partition(perValue, index, low, high);
            if (low != pirot - 1)
                sort(perValue, index, low, pirot - 1);
            if (pirot + 1 != high)
                sort(perValue, index, pirot + 1, high);
        }
    }

    private static int partition(double[] perValue, int[] index, int low, int high) {
        double temp1 = perValue[low];
        int temp2 = index[low];
        if (low < high) {
            while (low < high && perValue[high] < temp1)
                high--;
            perValue[low] = perValue[high];
            index[low] = index[high];
            while (low < high && perValue[low] > temp1)
                low++;
            perValue[high] = perValue[low];
            index[high] = index[low];
        }
        perValue[low] = temp1;
        index[low] = temp2;
        return low;
    }


    class node {
        int weight;
        int value;
        double wv;//价重比

        node(int weight, int value, double wv) {
            this.weight = weight;
            this.value = value;
            this.wv = wv;
        }
    }

    public List<int[]> ship2(int[] weight, int[] value, int M) {
        List<node> list = new ArrayList<>();
        for (int i = 0; i < weight.length; i++) {
            double wv = value[i] / weight[i];
            list.add(new node(weight[i], value[i], wv));
        }
        list.sort((n1, n2) -> (int) (n1.wv - n2.wv));
        double sum=0;
        for (int i = 0; i < list.size(); i++) {
            if (M > list.get(i).weight) {
                sum+=list.get(i).value;
                M = M - list.get(i).weight;
            }else {
                sum+=list.get(i).wv*M;
                break;
            }
        }
        return new ArrayList<>();
    }
}
